/* vim: set expandtab tabstop=4 softtabstop=4 shiftwidth=4: */
/* Copyright (C) 2012 Zongyou Yao. All rights reserved.     */

#ifndef XP_INCLUDED
#define XP_INCLUDED

/**
 * An extended-precision unsigned integer is represented in base 256 by an array 
 * of n digits, least significant digit first. Most xp functions take n as an 
 * argument along with source and destination xp_ts; it is an unchecked runtime 
 * error for n < 1 or for n not to be the length of the corresponding xp_ts. It
 * is an unchecked runtime error to pass a null xp_t or a xp_t that is too small 
 * to any xp function.
 */
typedef unsigned char * xp_t;

/**
 * Sets z[0..n-1] to x + y + carry and returns the carry out of z[n-1]. 
 * carry must be zero or one.
 */
int xp_add(int n, xp_t z, xp_t x, xp_t y, int carray);

/**
 * Sets z[0..n-1] to x - y - borrow and returns the borrow into z[n-1]. 
 * borrow must be zero or one.
 */
int xp_sub(int n, xp_t z, xp_t x, xp_t y, int borrow);

/**
 * Adds x[0..n-1] * y[0..m-1] to z[0..n+m-1] and returns the carry-out of z[n+m-1].
 * If z == 0, xp_mul computes x * y. It is an unchecked runtime error for z to be 
 * the same xp_t as x or y.
 */
int xp_mul(xp_t z, int n, xp_t x, int m, xp_t y);

/**
 * Sets q[0..n-1] to x[0..n-1] / y[0..m-1], r[0..m-1] to x[0..n-1] mod y[0..m-1],
 * and returns one, if y != 0. If y == 0, xp_div returns zero and leaves q and r
 * unchanged. tmp must hold at least n+m+2 digits. It is an unchecked runtime error
 * for q or r to be one of x or y, for q and r to be the same xp_t, or for tmp to
 * be too small.
 */
int xp_div(int n, xp_t q, xp_t x, int m, xp_t y, xp_t r, xp_t tmp);

/**
 * Sets z[0..n-1] to x + y, where y is a single digit, and returns the carry-out
 * of z[n-1]. It is an unchecked runtime error for y > 2(8).
 */
int xp_sum(int n, xp_t z, xp_t x, int y);

/**
 * Sets z[0..n-1] to x - y, where y is a single digit, and returns the borrow 
 * into z[n-1]. It is an unchecked runtime error for y > 256.
 */
int xp_diff(int n, xp_t z, xp_t x, int y);

/**
 * Sets z[0..n-1] to x * y, where y is a single digit, and returns the carry-out
 * of z[n-1]. It is an unchecked runtime error for y >= 2(8).
 */
int xp_product(int n, xp_t z, xp_t x, int y);

/**
 * Sets z[0..n-1] to x / y, where y is a single digit, and returns x mod y. It is
 * an unchecked runtime error for y == 0 or y >= 2(8).
 */
int xp_quotient(int n, xp_t z, xp_t x, int y);

/**
 * Sets z[0..n-1] to ~x + carry, where carry is zero or one, and returns the 
 * carry-out of z[n-1].
 */
int xp_neg(int n, xp_t z, xp_t x, int carry);

/**
 * Returns an int < 0, = 0, or > 0 if x < y, x = y, or x > y.
 */
int xp_cmp(int n, xp_t x, xp_t y);

/**
 * Sets z[0..n-1] to x[0..m-1] shifted left by s bits, and fills the vacated bits
 * with fill, which must be zero or one. It is an unchecked runtime error for s < 0.
 */
void xp_lshift(int n, xp_t z, int m, xp_t x, int s, int fill);

/**
 * Shifts right; see xp_lshift. If n > m, the excess bits are treated as if they
 * were equal to fill.
 */
void xp_rshift(int n, xp_t z, int m, xp_t x, int s, int fill);

/**
 * Returns the length of x; that is, the index plus one of the most significant
 * nonzero digit in x[0..n-1].
 */
int xp_length(int n, xp_t x);

/**
 * Sets z[0..n-1] to u mod 2(8n) and returns u/2(8n).
 */
unsigned long xp_fromint(int n, xp_t z, unsigned long u);

/**
 * Returns x mod (ULONG_MAX + 1). 
 */
unsigned long xp_toint(int n, xp_t x);

/**
 * Interprets str as an unsigned integer in base using z[0..n-1] as the initial 
 * value in the conversion, and returns the first nonzero carry-out of the conersion
 * step. If end != null, *end points to the character in str that terminated the scan
 * or produced a nonzero carry. 
 * See ap_fromstr.
 */
int xp_fromstr(int n, xp_t z, const char *str, int base, char **end);

/**
 * Fills str[0..size - 1] with the character representation of x in base, sets x
 * to zero, and returns str. It is a checked runtime error for str == null, size 
 * to be too small, or for base < 2 or base > 36.
 */
char *xp_tostr(char *str, int size, int base, int n, xp_t x);

#endif
